package com.yulan.subString;

import org.junit.Test;

import java.util.HashSet;

/**
 * 1062. 最长重复子串
 */
public class LeetCode_1062 {
    public int longestRepeatingSubstring(String str) {
        int n = str.length();
        int[] nums = new int[n];
        for(int i = 0;i<n;i++){
            nums[i] = (int)str.charAt(i) - (int)'a';
        }

        int HashRoot = 26;
        long modules =  (long)Math.pow(2,24);


        int left = 1,right = n;
        int len=0;
        while(left<=right){
            len = (left+right)>>>1;
            if(search(len,n,modules,n,nums)!=-1) left = len + 1;
            else right = len - 1;
        }

        return left - 1;
    }

    public int search(int len,int a,long modules,int n,int[] nums){
        long hash = 0;
        for(int i = 0;i<len;i++){
            hash = (hash*a + nums[i])%modules;
        }

        HashSet<Long> seen = new HashSet<>();
        seen.add(hash);

        long al = 1;
        for(int i = 1;i<=len;i++) al = (al*a)%modules;
        for(int start = 1;start<n-len+1;start++){
            hash = (hash * a - nums[start - 1] * al % modules + modules) % modules;
            hash = (hash + nums[start + len - 1]) % modules;
            if (seen.contains(hash)) return start;
            seen.add(hash);
        }
        return -1;
    }

    @Test
    public void test1(){
        String str = "aabcaabdaab";
        System.out.println(longestRepeatingSubstring(str));
    }
}
